/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function (head, x) {
  let large = new ListNode(-1)
  let small = new ListNode(-1) // 大小新链表
  let p1 = large,
    p2 = small // 标记新旧尾结点
  let cur = head // 标记头结点
  while (cur) {
    if (cur.val < x) {
      p2.next = cur // 将其连接到大小链表上
      p2 = p2.next
    } else {
      p1.next = cur
      p1 = p1.next
    }
    cur = cur.next // 节点后移
  }
  p2.next = large.next
  p1.next = null // 将大节点的尾结点置为null
  return small.next // 返回新的头结点的下一个节点
}
